#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<assert.h>
//排升序->建大堆  排降序->建小堆
void swap(int* px,int* py)
{
  int tmp = *px;
  *px = *py;
  *py = tmp;
}
//向上调整
void AdjustUp(int* a,int child)
{
  assert(a);
  int parent = (child-1)/2;
  while(child > 0)
  {
    if(a[child] > a[parent])
    {
      swap(&a[child],&a[parent]);
      child = parent;
      parent = (child-1)/2;
    }
    else 
    {
      break;
    }
  }
}
//向下调整
void AdjustDown(int* a,int parent,int n)
{
  assert(a);
  int child = parent*2+1;
  while(child < n)
  {
    if(child + 1 < n && a[child+1] > a[child])
      child+=1;
    if(a[child] > a[parent])
    {
      swap(&a[child],&a[parent]);
      parent = child;
      child = parent*2+1;
    }
    else 
    {
      break;
    }
  }
}
void HeapSort(int* a,int n)
{
  //1.建堆
  //case1:向下调整建堆O(N)
//   for(int i = (n-1-1)/2;i>=0;i--) //从最后一个叶子节点的父亲开始逐步向上走
//   {
//     AdjustDown(a,i,n);
//   }
  //case2:向上调整建堆O(N*logN)
  //认为第一个元素是堆中的元素,然后后面的元素依次插入,然后进行向上调整
  for(int i = 1;i<n;i++)
    AdjustUp(a,i);
  //2.调堆
  int end = n-1;//含义1：当前元素应该被放的位置  含义2：认为堆中有多少个元素
  while(end > 0)
  {
    swap(&a[0],&a[end]);
    AdjustDown(a,0,end);
    end--;
  }
}
int main()
{
  srand((unsigned int)time(NULL));
  int a[10] = {0};
  for(int i = 0;i<10;i++)
  {
    a[i] = rand() % 20;
    printf("%d ",a[i]);
  }
  printf("\n");
  HeapSort(a,sizeof(a)/sizeof(a[0])); 
  for(int i =0;i<10;i++) printf("%d ",a[i]);
  printf("\n");
  return 0;
}
